Weakly chained diagonally dominant matrix

Venn Diagram showing the containment of weakly chained diagonally dominant (WCDD) matrices relative to weakly diagonally dominant (WDD) and strictly diagonally dominant (SDD) matrices.

In mathematics, the weakly chained diagonally dominant matrices are a family of nonsingular matrices that include the strictly diagonally dominant matrices.

Definition

Preliminaries

We say row [math]\displaystyle{ i }[/math] of a complex matrix [math]\displaystyle{ A = (a_{ij}) }[/math] is strictly diagonally dominant (SDD) if [math]\displaystyle{ |a_{ii}|\gt \textstyle{\sum_{j\neq i}}|a_{ij}| }[/math]. We say [math]\displaystyle{ A }[/math] is SDD if all of its rows are SDD. Weakly diagonally dominant (WDD) is defined with [math]\displaystyle{ \geq }[/math] instead.

The directed graph associated with an [math]\displaystyle{ m \times m }[/math] complex matrix [math]\displaystyle{ A = (a_{ij}) }[/math] is given by the vertices [math]\displaystyle{ \{1, \ldots, m\} }[/math] and edges defined as follows: there exists an edge from [math]\displaystyle{ i \rightarrow j }[/math] if and only if [math]\displaystyle{ a_{ij} \neq 0 }[/math].

Definition

A complex square matrix [math]\displaystyle{ A }[/math] is said to be weakly chained diagonally dominant (WCDD) if

• [math]\displaystyle{ A }[/math] is WDD and
• for each row [math]\displaystyle{ i_1 }[/math] that is not SDD, there exists a walk [math]\displaystyle{ i_1 \rightarrow i_2 \rightarrow \cdots \rightarrow i_k }[/math] in the directed graph of [math]\displaystyle{ A }[/math] ending at an SDD row [math]\displaystyle{ i_k }[/math].

Example

The directed graph associated with the WCDD matrix in the example. The first row, which is SDD, is highlighted. Note that regardless of which node [math]\displaystyle{ i }[/math] we start at, we can find a walk [math]\displaystyle{ i \rightarrow (i - 1) \rightarrow (i - 2) \rightarrow \cdots \rightarrow 1 }[/math].

The [math]\displaystyle{ m \times m }[/math] matrix

[math]\displaystyle{ \begin{pmatrix}1\\ -1 & 1\\ & -1 & 1\\ & & \ddots & \ddots\\ & & & -1 & 1 \end{pmatrix} }[/math]

is WCDD.

Properties

Nonsingularity

A WCDD matrix is nonsingular.

Proof: Let [math]\displaystyle{ A=(a_{ij}) }[/math] be a WCDD matrix. Suppose there exists a nonzero [math]\displaystyle{ x }[/math] in the null space of [math]\displaystyle{ A }[/math]. Without loss of generality, let [math]\displaystyle{ i_1 }[/math] be such that [math]\displaystyle{ |x_{i_1}|=1\geq|x_j| }[/math] for all [math]\displaystyle{ j }[/math]. Since [math]\displaystyle{ A }[/math] is WCDD, we may pick a walk [math]\displaystyle{ i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_k }[/math] ending at an SDD row [math]\displaystyle{ i_k }[/math].

Taking moduli on both sides of

[math]\displaystyle{ -a_{i_1 i_1}x_{i_1} = \sum_{j\neq i_1} a_{i_{1} j}x_j }[/math]

and applying the triangle inequality yields

[math]\displaystyle{ \left|a_{i_1 i_1}\right|\leq\sum_{j\neq i_1}\left|a_{i_1 j}\right|\left|x_j\right|\leq\sum_{j\neq i_1}\left|a_{i_1 j}\right|, }[/math]

and hence row [math]\displaystyle{ i_1 }[/math] is not SDD. Moreover, since [math]\displaystyle{ A }[/math] is WDD, the above chain of inequalities holds with equality so that [math]\displaystyle{ |x_{j}|=1 }[/math] whenever [math]\displaystyle{ a_{i_1 j}\neq0 }[/math]. Therefore, [math]\displaystyle{ |x_{i_2}|=1 }[/math]. Repeating this argument with [math]\displaystyle{ i_2 }[/math], [math]\displaystyle{ i_3 }[/math], etc., we find that [math]\displaystyle{ i_k }[/math] is not SDD, a contradiction. [math]\displaystyle{ \square }[/math]

Recalling that an irreducible matrix is one whose associated directed graph is strongly connected, a trivial corollary of the above is that an irreducibly diagonally dominant matrix (i.e., an irreducible WDD matrix with at least one SDD row) is nonsingular.

Relationship with nonsingular M-matrices

The following are equivalent:

• [math]\displaystyle{ A }[/math] is a nonsingular WDD M-matrix.
• [math]\displaystyle{ A }[/math] is a nonsingular WDD L-matrix;
• [math]\displaystyle{ A }[/math] is a WCDD L-matrix;

In fact, WCDD L-matrices were studied (by James H. Bramble and B. E. Hubbard) as early as 1964 in a journal article in which they appear under the alternate name of matrices of positive type.

Moreover, if [math]\displaystyle{ A }[/math] is an [math]\displaystyle{ n\times n }[/math] WCDD L-matrix, we can bound its inverse as follows:

[math]\displaystyle{ \left\Vert A^{-1}\right\Vert _{\infty}\leq\sum_{i}\left[a_{ii}\prod_{j=1}^{i}(1-u_{j})\right]^{-1} }[/math]   where   [math]\displaystyle{ u_{i}=\frac{1}{\left|a_{ii}\right|}\sum_{j=i+1}^{n}\left|a_{ij}\right|. }[/math]

Note that [math]\displaystyle{ u_n }[/math] is always zero and that the right-hand side of the bound above is [math]\displaystyle{ \infty }[/math] whenever one or more of the constants [math]\displaystyle{ u_i }[/math] is one.

Tighter bounds for the inverse of a WCDD L-matrix are known.

Applications

Due to their relationship with M-matrices (see above), WCDD matrices appear often in practical applications. An example is given below.

Monotone numerical schemes

WCDD L-matrices arise naturally from monotone approximation schemes for partial differential equations.

For example, consider the one-dimensional Poisson problem

[math]\displaystyle{ u^{\prime \prime}(x) + g(x)= 0 }[/math]   for   [math]\displaystyle{ x \in (0,1) }[/math]

with Dirichlet boundary conditions [math]\displaystyle{ u(0)=u(1)=0 }[/math]. Letting [math]\displaystyle{ \{0,h,2h,\ldots,1\} }[/math] be a numerical grid (for some positive [math]\displaystyle{ h }[/math] that divides unity), a monotone finite difference scheme for the Poisson problem takes the form of

[math]\displaystyle{ -\frac{1}{h^2}A\vec{u} + \vec{g} = 0 }[/math]   where   [math]\displaystyle{ [\vec{g}]_j = g(jh) }[/math]

and

[math]\displaystyle{ A = \begin{pmatrix}2 & -1\\ -1 & 2 & -1\\ & -1 & 2 & -1\\ & & \ddots & \ddots & \ddots\\ & & & -1 & 2 & -1\\ & & & & -1 & 2 \end{pmatrix}. }[/math]

Note that [math]\displaystyle{ A }[/math] is a WCDD L-matrix.